package com.njupt.Tree;

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/6 21:13
 * @Description: 236. 二叉树的最近公共祖先
 * @Version: 1.0
 */


public class LowestCommonAncestor {

    /**
     * 后续遍历非递归算法，当遍历到当前节点的时候栈中保存的节点正是当前节点的祖先节点
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> stackP = new LinkedList<>();
        Deque<TreeNode> stackQ = new LinkedList<>();

        traverse(root,p,stackP);
        traverse(root,q,stackQ);
        Iterator<TreeNode> iteratorP = stackP.iterator();
        while(iteratorP.hasNext()){
            TreeNode next = iteratorP.next();
            Iterator<TreeNode> iteratorQ = stackQ.iterator();
            while(iteratorQ.hasNext()){
                if(next.val == iteratorQ.next().val){
                    return next;
                }
            }
        }
        return null;
    }

    private void traverse(TreeNode root, TreeNode node, Deque<TreeNode> stack) {

        TreeNode cur = root;
        Deque<Boolean> stackFlag = new LinkedList<>();
        Boolean flag = false;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                stack.push(cur);
                stackFlag.push(false);
                cur = cur.left;
            }else {
                cur = stack.pop();
                flag = stackFlag.pop();
                if(flag == false){
                    stack.push(cur);
                    stackFlag.push(true);
                    cur = cur.right;
                }else {
                    //访问节点
                    if(cur.val == node.val){
                        stack.push(cur);
                        break;
                    }
                    cur = null;
                }
            }
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if(left == null && right != null) {
            return right;
        } else if (left != null  && right == null) {
            return left;
        } else if (left != null && right != null) {
            return root;
        }else{
            return null;
        }
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        LowestCommonAncestor test = new LowestCommonAncestor();
        TreeNode treeNode = test.lowestCommonAncestor(root, root.left, root.left.right.right);

        if(treeNode != null){
            System.out.println(treeNode.val);
        }else {
            System.out.println("null");
        }
    }
}
